package org.example.search;

import org.example.sort.BubbleSort;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class BinarySearch {

    public static void main(String[] args) {
        int[] arr = {1,3,3,3,3,5,7,9,11,11,13,13,13,13,15,18};

        //递归方式
        /*List<Integer> resList = binarySearch(arr,0,arr.length-1,3);
        System.out.println("resIndex=" + resList);*/

        //非递归方式
        List<Integer> resList = binarySearch2(arr,18);
        //将符合条件的下标有序输出
        int[] arr2 = change((ArrayList<Integer>) resList);
        System.out.println("Index=" + Arrays.toString(arr2));

    }

    //递归方式
    public static List binarySearch(int[] arr, int left, int right, int value){

        //如果找不到，返回-1；
        if (left > right){
            return new ArrayList<Integer>();
        }
        int midIndex = (left + right)/2;
        int mid = arr[midIndex];
        //值在中间值的哪一边就往那一边递归，直到所找的值等于中间值，就返回中间值的下标
        if (value < mid){
            return binarySearch(arr,left,midIndex-1,value);
        }else if (value > mid){
            return binarySearch(arr,midIndex+1,right,value);
        }else {
            //System.out.println(midIndex);
            List<Integer> resList = new ArrayList<>();
            //先把首次找到与value相同的值放到集合中
            resList.add(midIndex);
            //假设还有与value相同的值midIndex的左边
            int temp = midIndex -1;
            while(temp >= 0 && arr[temp] == value){
                resList.add(temp);
                temp--;
            }
            //假设还有与value相同的值midIndex的右边
            int temp2 = midIndex +1;
            while(temp2 < arr.length -1 && arr[temp2] == value){
                resList.add(temp2);
                temp2++;
            }
            return resList;
        }
    }

    /**
     *
     * @param arr 待查找的数组，默认为升序排序的数组
     * @param target 需要查找的数
     * @return 返回对应的下标，-1表示没有找到
     */
    //非递归方式实现二分查找算法
    public static List binarySearch2(int[] arr, int target){

        int left = 0;
        int right = arr.length - 1;
        List<Integer> resList = new ArrayList<>();
        while(left <= right){
            int mid = (left + right) /2;
            if (arr[mid] == target){
                resList.add(mid);
                //假设相同的值在所找到mid的左边
                int temp = mid - 1;
                while(temp >= 0 && arr[temp] == target){
                    resList.add(temp);
                    temp--;
                }
                //假设相同的值在所找到mid的右边
                temp = mid + 1;
                while(temp < arr.length && arr[temp] == target){
                    resList.add(temp);
                    temp++;
                }
                return resList;
            }else if (arr[mid] > target){
                right = mid -1;//需要向左边查找
            }else{
                left = mid + 1;//需要向右边查找
            }
        }
        return resList;
    }

    //将无序数组集合转为有序数组
    public static int[] change(ArrayList<Integer> arrayList){

        int[] arr = new int[arrayList.size()];
        for (int i = 0; i < arrayList.size(); i++){
            arr[i] = arrayList.get(i);
        }
        //自己写的一个简单的冒泡排序
        BubbleSort.bubbleSort(arr);
        return arr;
    }

}
